package algorithm.dac;

/**
 * 分治算法
 * 汉诺塔游戏
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-04-04
 */
public class HanoiTower {

    public static void main(String[] args) {
        hanoiTower(5, 'A', 'B', 'C');
    }

    /**
     * 汉诺塔游戏 总是把整个盘看成2个盘 最上面和最下面
     * 如果只有一个盘 直接从A-C
     * 分解：1、先把最上面的盘 A-B 借助C
     *      2、再把最下面的盘 A-C
     *      3、最后把剩余的盘 B-C 借助A
     *
     * @param num 多少个圆盘
     * @param a   A塔 表示从哪个塔开始
     * @param b   B塔 表示需要借组的塔
     * @param c   C塔 表示移动到哪个塔
     */
    private static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) {
            // 只有一个圆盘的时候 直接从A->C
            System.out.println("第1个圆盘从 " + a + "->" + c);
        } else {
            // 1、先把最上面所有圆盘 A-B，移动过程需要借助C
            hanoiTower(num - 1, a, c, b);
            // 2、把最下面的圆盘 A - C
            System.out.println("第" + num + "个圆盘从 " + a + "->" + c);
            // 3、把B塔的所有圆盘从 B-C 移动过程需要借助A
            hanoiTower(num - 1, b, a, c);
        }
    }
}

